package com.cwj.algorithm.linear;

import java.util.NoSuchElementException;

/**
 * @author chenwujie
 * @date 2020/11/1214:35
 */
public class MyLinkedList<E> {
    private int size;
    transient Node<E> first;
    transient Node<E> last;

    public MyLinkedList() {
    }

    public boolean add(E e){
        final Node l = last;
        final Node newNode = new Node(e, null);
        last = newNode;
        if(l == null){
            first = newNode;
        }else{
            l.next = newNode;
        }
        size++;
        return true;
    }

    public boolean add(int index, E e){
        isPositionIndex(index);
        if(index == size){
            add(e);
        }else{
            Node<E> x = first;
            Node<E> pred = null;
            for (int i = 0; i < index - 1; i++) {
                x = first;
            }
            pred = x;
            x = pred.next;
            pred.next = new Node<>(e, x);
        }
        size++;
        return true;
    }

    public boolean remove(){
        final Node<E> f = first;
        if (f == null){
            throw new NoSuchElementException();
        }
        first = f.next;
        size--;
        return true;
    }

    public boolean remove(int index){
        isElementIndex(index);
        if(index == 0){
            remove();
        }else{
            Node<E> x = first;
            Node<E> pred;
            for (int i = 0; i < index - 1; i++) {
                x = x.next;
            }
            pred = x;
            x = pred.next;
            pred.next = x.next;
        }
        size--;
        return true;
    }

    public E get(int index){
        isElementIndex(index);
        Node<E> x = first;
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        return x.item;
    }

    public void clear(){
        for (Node<E> x = first; x != null; ) {
            Node<E> next = x.next;
            x.item = null;
            x.next = null;
            x = next;
        }
        first = last = null;
        size = 0;
    }
    public int size(){
        return size;
    }

    /**
     * 链表反转
     */
    public void reverse(){
        if(first == null){
            return;
        }
        reverse(first);
    }
    private Node<E> reverse(Node<E> node){
        if(node.next == null){
            return first = node;
        }
        Node<E> reversed = reverse(node.next);
        reversed.next = node;
        node.next = null;
        return node;
    }

    /**
     * 获取链表中间值
     * @return
     */
    public E getMind(){
        return getMind(first);
    }
    private E getMind(Node<E> node){
        Node<E> slow = node;
        Node<E> fast = node;
        while (slow.next !=null && fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow.item;
    }
    private void isElementIndex(int index) {
        boolean b = index >=0 && index < size;
        if(!b){
            throw new IndexOutOfBoundsException("下标越界");
        }
    }
    private void isPositionIndex(int index) {
        boolean b = index >=0 && index <= size;
        if(!b){
            throw new IndexOutOfBoundsException("下标越界");
        }
    }

    private static class Node<E> {
        E item;
        Node<E> next;

        Node(E element, Node<E> next) {
            this.item = element;
            this.next = next;
        }
    }
}
